#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define in read()

int read(){int x = 0,sgn = 1;char ch = getchar(); for(;!isdigit(ch);ch=getchar()) if(ch == '-') sgn = -1;for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);return x * sgn;}

const int mod = 1004535809;
const int N = 1.3e5+10;

ll qp(ll x,int t){ll res=1;for(;t;t>>=1,x=x*x%mod)if(t&1) res=res*x%mod;return res;}

ll Wn[N<<2],F[N<<2],G[N<<2],H[N<<2],A[N<<2],invH[N<<2],fac[N],inv[N];
int rev[N<<2],len,n;

void init_NTT(int l){
    for(len = 1;len < 2 * l;len <<= 1);
    for(int i = 1;i < len;i++) rev[i] = rev[i>>1]>>1 | (i & 1 ? len >> 1 : 0);
}

void init(int l){
    for(int i = (fac[0] = 1);i <= l;i++) fac[i] = fac[i-1] * i % mod; inv[l] = qp(fac[l],mod-2);
    for(int i = l - 1;i >= 0;i--) inv[i] = inv[i+1] * (i + 1) % mod;
}

void NTT(ll *f,int on = 1){
    for(int i = 1;i < len;i++) if(i < rev[i]) swap(f[i],f[rev[i]]);
    for(int h = 2;h <= len;h <<= 1){
		ll wn = Wn[h];
		for(int i = 0;i < len;i+=h){
			ll ww = 1;
			for(int k = i;k < i + h/2;k++){
				ll u = f[k],v = f[k+h/2] * ww % mod; ww = ww * wn % mod;
				f[k] = (u + v) % mod,f[k+h/2] = (u - v + mod) % mod;
			}
		}
    }
    if(on == -1){reverse(f+1,f+len); ll inv = qp(len,mod-2);for(int i = 0;i < len;i++) f[i] = f[i] * inv % mod;}
}

void getinv(int deg,ll *f,ll *g){
    if(deg == 1) return g[0] = qp(f[0],mod-2),void();
    getinv(deg+1>>1,f,g);
    init_NTT(deg); for(int i = 0;i < deg;i++) A[i] = f[i]; for(int i = deg;i < len;i++) A[i] = 0;
    NTT(A); NTT(g);  for(int i = 0;i < len;i++) g[i] = g[i] * (2 - A[i] * g[i] % mod + mod) % mod;
    NTT(g,-1); for(int i = deg;i < len;i++) g[i] = 0;
}

int main (){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
#endif
	n = in; init(n); H[0] = 1;
    for(int h = 2;h < N<<2;h<<=1) Wn[h] = qp(3,(mod-1)/h);
    for(int i = 1;i <= n;i++) G[i] = qp(2,1ll * i * (i-1) / 2 % (mod-1)) * inv[i-1] % mod;
    for(int i = 1;i <= n;i++) H[i] = qp(2,1ll * i * (i-1) / 2 % (mod-1)) * inv[i] % mod;
	getinv(n+1,H,invH); init_NTT(n+1);
    NTT(G);NTT(invH); for(int i = 0;i < len;i++) G[i] = G[i] * invH[i] % mod;
    NTT(G,-1); ll ans = G[n] * fac[n-1] % mod;
    printf("%lld\n",ans);
}
